package com.kehao.leetcode.hard.backtracking;

import org.junit.Test;

//正则表达式
public class isMatch2Solution {
    public boolean isMatch(String s, String p) {
        boolean dp[][] = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        for (int i = 1; i < s.length()+1; i++) {
            dp[i][0] = false;
        }
        for (int i = 1; i < p.length(); i=i+2) {
            if(p.charAt(i)=='*'){
                dp[0][i+1] = true;
            }else {
                break;
            }
        }
        for (int i = 1; i < s.length()+1; i++) {
            for (int j = 1; j < p.length()+1; j++) {
                if(p.charAt(j-1)=='.'){
                    dp[i][j] = dp[i-1][j-1];
                }else if(p.charAt(j-1)=='*'){
                    dp[i][j] = dp[i][j-2];
                    if(dp[i][j]) continue;
                    //p里面*前面那个字符
                    char c2 = p.charAt(j - 2);
                    if(c2=='.'){
                        dp[i][j] =  dp[i-1][j];
                    }else {
                        if(c2!=s.charAt(i-1)){
                            dp[i][j] = false;
                        }else {
                            dp[i][j] = dp[i-1][j];
                        }
                    }
                }else {
                    dp[i][j] = s.charAt(i-1)==p.charAt(j-1)&&dp[i-1][j-1];
                }
            }
        }
        return dp[s.length()][p.length()];
    }

    @Test
    public void test01(){
        String s="aa";
        String p="a";
        System.out.println(isMatch(s,p));
    }

    @Test
    public void test02(){
        String s="aa";
        String p="a*";
        System.out.println(isMatch(s,p));
    }

    @Test
    public void test03(){
        String s="ab";
        String p=".*";
        System.out.println(isMatch(s,p));
    }

    @Test
    public void test04(){
        String s="aab";
        String p="c*a*b";
        System.out.println(isMatch(s,p));
    }

    @Test
    public void test05(){
        String s="mississippi";
        String p="mis*is*p*.";
        System.out.println(isMatch(s,p));
    }

    @Test
    public void test06(){
        String s="aaa";
        String p="aa*c*a";
        System.out.println(isMatch(s,p));
    }


}
